package com.fyt.algorithm.Leecode.day3;

public class LongestPalindrome {

    /**
     * 中心扩散法
     *
     * @param s
     * @return
     */
    public static String longestPalindromePyExpand(String s) {
     //   boolean [][]isHuiWen= new boolean[s.length()][s.length()];
        int len = 0, len1, len2, x = 0,y=0,len3=0;
        if (s == null || s.length() < 1) {
            return "";
        }
    //每个字符当一次“奇数中心”，又当一次“偶数中心”（中心其实是它和下一个字符之间的“缝”）。
        for (int i = 0; i < s.length(); i++) {
            //奇数,从实际数字向两边扩散
            len1 = expandedLength(s, i, i);
            //偶数,从缝隙向两边扩撒
            len2 = expandedLength(s, i, i + 1);
            len = Math.max(len1, len2);
            if(len>len3){

                x = i - (len - 1) / 2;
                y=i+len/2;
                len3=len;
            }


        }


        return s.substring(x, y+1);
    }

    /**
     * 动态规划法
     * @param s
     * @return
     */

    public static String longestPalindrome(String s) {
        if(s==null||s.length()<1){
            return "";
        }

        boolean [][]dp=new boolean[s.length()][s.length()];
        int maxSub=1;
        int start=0;

        for (int i = 0; i < s.length(); i++) {
           dp[i][i]=true;

        }
        for (int i = 0; i <s.length()-1 ; i++) {
            if(s.charAt(i)==s.charAt(i+1)){
                dp[i][i+1]=true;
                start=i;
                maxSub=2;
            }
        }
        for (int len = 3; len <=s.length() ; len++) {
            for (int i = 0; i <=s.length()-1-len+1 ; i++) {
                int j=i+len-1;
                if(s.charAt(i)==s.charAt(j)&&dp[i+1][j-1]){
                    dp[i][j]=true;

                    if (len>maxSub){
                        start=i;
                        maxSub=len;
                    }

                }
            }

        }


        return s.substring(start,start+maxSub);
    }

    public static int expandedLength(String s, int left, int right) {
        while (left >=0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            right++;
            left--;
        }

        return right - left - 1;
    }

    /**
     * 动态规划法
     * @param args
     */




    public static void main(String[] args) {
       String s="babad";
        System.out.println( longestPalindrome(s));

    }
}
